//
// Created by cheng on 2021/01/25.
//

#include <iostream>

using namespace std;

struct Card {
    char suit, value;
};

void BubbleSort(Card* A, int N) {
    for (int i = 0; i < N; ++i) {
        for (int j = N-1; j >= i+1; --j) {
            if(A[j].value < A[j-1].value) {
                Card temp = A[j];
                A[j] = A[j-1];
                A[j-1] = temp;
            }
        }
    }
}

void SelectionSort(Card* A, int N) {
    for (int i = 0; i < N; ++i) {
        int minJ = i;
        for (int j = i; j < N; ++j) {
            if (A[j].value < A[minJ].value) {
                minJ = j;
            }
        }
        auto temp = A[i];
        A[i] = A[minJ];
        A[minJ] = temp;

        //swap(A[i], A[minJ]);
    }
}

void Print(Card* A, int N) {
    for( int i = 0; i < N; i++) {
        if (i > 0) {
            cout << " ";
        }
        cout << A[i].suit << A[i].value;
    }
    cout << endl;
}

bool IsStable(Card* C1, Card* C2, int N) {
    for (int i = 0; i < N; ++i) {
        if (C1[i].suit != C2[i].suit) {
            return false;
        }
    }
    return true;
}

int main() {
    Card C1[100], C2[100];
    int N;

    cin >> N;
    /**
     * input example: 5
     * c3 c9 s4 d2 h3
     */
    for(int i = 0; i < N; i++) {
        cin >> C1[i].suit >> C1[i].value;
    }

    for (int i = 0; i < N; ++i) {
        C2[i] = C1[i];
    }
    cout << "input" << endl;
    Print(C1, N);
    cout << "bubble sort: ";
    BubbleSort(C1, N);
    Print(C1, N);
    cout << " stable!" << endl;
    cout << "selection sort: ";
    SelectionSort(C2, N);
    Print(C2, N);
    if (IsStable(C1, C2, N)) {
        cout << "stable!" << endl;
    } else {
        cout << "not stable!" << endl;
    }
    return 0;
}